package class09;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;

/**
 *
 * 贪心算法
 * 1.最自然智慧的算法
 * 2.用一种局部最功利的标准, 总是做出在当前看来是最好的选择
 * 3.难点在于证明局部最功利的标准可以得到全局最优解
 * 4.对于贪心算法的学习主要以增加阅历和经验为主
 *
 * 缺点: 贪心在于贪每局部最优,但是全局上看不一定是全局最优
 * 全局最优解可以考虑动态规划
 *
 *
 *
 * 给定一个由字符串组成的数组strs
 * 必须把所有的字符串拼接起来
 * 返回所有可能的拼接结果中,字典序(a-z,首位权重最高,不同位数补0进行比较)最小的结果
 *
 * 思路:
 * 1. 单个数据排序(单个数值的比较具有传递性)
 * x,y -> x字典序 < y字典序,x在前; 否则,y在前;  存在问题(反例): ba b , b0 < ba -> bba, 而实际最小应该是 bab
 *
 * 2. 两份数据组合排序(特殊排序策略需要证明排序的传递性, 即需证明: 条件 a.b <= b.a, b.c <= c.b 结论 a.c <= c.a)
 * x,y -> xy字典序 < yx字典序, 那么x在前; 否则y在前
 *
 * 证明: 条件 a.b <= b.a, b.c <= c.b 结论 a.c <= c.a
 * "hx" 拼接 "zx" 可以理解为26进制情况下, "hx"值*26^2 + "zx"的值
 * 那么 a.b = a*26^b长度 + b, m()为求解函数
 * 那么 a.b <= b.a  <=> a*m(b)+b <= b*m(a)+a  <=> (同时减b乘c) a*m(b)*c <= b*m(a)*c+ac-bc
 * 那么 b.c <= c.b  <=> b*m(c)+c <= c*m(b)+b  <=> (同时减b乘a) b*m(c)*a+ca-ba <= c*m(b)a
 * 求证 a.c <= c.a  <=> a*m(c)+c <= c*m(a)+a
 *
 * b*m(c)*a+ca-ba <= c*m(b)a == a*m(b)*c <= b*m(a)*c+ac-bc
 * b*m(c)*a+ca-ba <= b*m(a)*c+ac-bc
 * b*m(c)*a-ba <= b*m(a)*c-bc
 * m(c)*a-a <= m(a)*c-c  同时除b
 * m(c)*a+c <= m(a)*c+a  同时+a+c
 * 即证: a*m(c)+c <= c*m(a)+a
 *
 *
 *
 */
public class Code01_LowestLexicography {

	public static String lowestString1(String[] strs) {
		if (strs == null || strs.length == 0) {
			return "";
		}
		ArrayList<String> all = new ArrayList<>();
		HashSet<Integer> use = new HashSet<>();
		process(strs, use, "", all);
		String lowest = all.get(0);
		for (int i = 1; i < all.size(); i++) {
			if (all.get(i).compareTo(lowest) < 0) {
				lowest = all.get(i);
			}
		}
		return lowest;
	}

	// strs里放着所有的字符串
	// 已经使用过的字符串的下标，在use里登记了，不要再使用了
	// 之前使用过的字符串，拼接成了-> path
	// 用all收集所有可能的拼接结果
	/**
	 * 时间复杂度: O(N!) * O(M) 全排列*M个字符串拼接耗时
	 *
	 * 假设下标: 0 1 2
	 * 0 -> 1 -> 2 走完一条路,归还2, 归还1
	 *   -> 2 -> 1 走完一条路,归还1, 归还2
	 *   -> 归还0
	 *
	 *
	 * @param strs 字符串数组
	 * @param use 已使用的下标set
	 * @param path 路径
	 * @param all 全排列路径集合
	 */
	public static void process(String[] strs, 
			HashSet<Integer> use, 
			String path, 
			ArrayList<String> all) {
		//使用(收集)大小等于原数组大小, 表示收集完成
		if (use.size() == strs.length) {
			//一种排列情况,添加到结果集
			all.add(path);
		} else {
			//循环加递归 <=> 全排列
			for (int i = 0; i < strs.length; i++) {
				if (!use.contains(i)) {
					//标记尝试过的下标位置
					use.add(i);
					process(strs, use, path + strs[i], all);
					//归还当前递归完成后, 当前递归尝试的下标位置
					use.remove(i);
				}
			}
		}
	}

	public static class MyComparator implements Comparator<String> {
		@Override
		public int compare(String a, String b) {
			return (a + b).compareTo(b + a);
		}
	}

	/**
	 * 贪心算法: 两份数据组合排序
	 * 时间复杂度: O(N)
	 * @param strs 字符串数组
	 * @return
	 */
	public static String lowestString2(String[] strs) {
		if (strs == null || strs.length == 0) {
			return "";
		}
		Arrays.sort(strs, new MyComparator());
		String res = "";
		for (int i = 0; i < strs.length; i++) {
			res += strs[i];
		}
		return res;
	}

	// for test
	public static String generateRandomString(int strLen) {
		char[] ans = new char[(int) (Math.random() * strLen) + 1];
		for (int i = 0; i < ans.length; i++) {
			int value = (int) (Math.random() * 5);
			ans[i] = (char) (97 + value);
		}
		return String.valueOf(ans);
	}

	// for test
	public static String[] generateRandomStringArray(int arrLen, int strLen) {
		String[] ans = new String[(int) (Math.random() * arrLen) + 1];
		for (int i = 0; i < ans.length; i++) {
			ans[i] = generateRandomString(strLen);
		}
		return ans;
	}

	// for test
	public static String[] copyStringArray(String[] arr) {
		String[] ans = new String[arr.length];
		for (int i = 0; i < ans.length; i++) {
			ans[i] = String.valueOf(arr[i]);
		}
		return ans;
	}

	public static void main(String[] args) {
		int arrLen = 6;
		int strLen = 5;
		int testTimes = 100000;
		for (int i = 0; i < testTimes; i++) {
			String[] arr1 = generateRandomStringArray(arrLen, strLen);
			String[] arr2 = copyStringArray(arr1);
			if (!lowestString1(arr1).equals(lowestString2(arr2))) {
				System.out.println("Oops!");
			}
		}
		System.out.println("finish!");
	}

}
